<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us" lang="en-us">
<head>
  <link href="//gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="generator" content="Hugo 0.68.3" />

  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">

  <title>Python数据结构——二叉树 &middot; 我的博客</title>

  
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/print.css" media="print">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/poole.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/syntax.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/hyde.css">
    <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Abril+Fatface|PT+Sans:400,400i,700">


  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="/favicon.png">

  
  
</head>

  <body class="theme-base-0b ">
  <aside class="sidebar">
  <div class="container sidebar-sticky">
    <div class="sidebar-about">
      <a href="/my_technology_blog/"><h1>我的博客</h1></a>
      <p class="lead">
       杨博的博客 
      </p>
    </div>

    <nav>
      <ul class="sidebar-nav">
        <li><a href="/my_technology_blog/">Home</a> </li>
        
      </ul>
    </nav>

    <p>&copy; 2021. All rights reserved. </p>
  </div>
</aside>

    <main class="content container">
    <div class="post">
  <h1>Python数据结构——二叉树</h1>
  <time datetime=2020-06-09T18:01:55&#43;0800 class="post-date">Tue, Jun 9, 2020</time>
  <h3 id="1-二叉树">1. 二叉树</h3>
<p>二叉树(binary tree)中的每个节点都不能有多于两个的儿子。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Ctree.jpg" alt="img"></p>
<p><strong>1.1 二叉树列表实现</strong></p>
<p>如上图的二叉树可用列表表示：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">tree<span style="color:#f92672">=</span>[<span style="color:#e6db74">&#39;A&#39;</span>,  <span style="color:#75715e">#root</span>
      [<span style="color:#e6db74">&#39;B&#39;</span>,    <span style="color:#75715e">#左子树</span>
       [<span style="color:#e6db74">&#39;D&#39;</span>,[],[]],
       [<span style="color:#e6db74">&#39;E&#39;</span>,[],[]]],
      [<span style="color:#e6db74">&#39;C&#39;</span>,     <span style="color:#75715e">#右子树</span>
       [<span style="color:#e6db74">&#39;F&#39;</span>,[],[]],
       []]
      ]
</code></pre></div><p>实现：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">BinaryTree</span>(item):
    <span style="color:#66d9ef">return</span> [item,[],[]]
<span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insertLeft</span>(tree,item):
    leftSubtree<span style="color:#f92672">=</span>tree<span style="color:#f92672">.</span>pop(<span style="color:#ae81ff">1</span>)
    <span style="color:#66d9ef">if</span> leftSubtree:
        tree<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">1</span>,[item,leftSubtree,[]])
    <span style="color:#66d9ef">else</span>:
        tree<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">1</span>,[item,[],[]])
    <span style="color:#66d9ef">return</span> tree
<span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insertRight</span>(tree,item):
    rightSubtree<span style="color:#f92672">=</span>tree<span style="color:#f92672">.</span>pop(<span style="color:#ae81ff">2</span>)
    <span style="color:#66d9ef">if</span> rightSubtree:
        tree<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">2</span>,[item,[],rightSubtree])
    <span style="color:#66d9ef">else</span>:
        tree<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">2</span>,[item,[],[]])
    <span style="color:#66d9ef">return</span> tree
<span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getLeftChild</span>(tree):
    <span style="color:#66d9ef">return</span> tree[<span style="color:#ae81ff">1</span>]
<span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getRightChild</span>(tree):
    <span style="color:#66d9ef">return</span> tree[<span style="color:#ae81ff">2</span>]
</code></pre></div><p>要实现下图的树：</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cshishu.png" alt="img"></p>
<p>　　</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">tree<span style="color:#f92672">=</span>BinaryTree(<span style="color:#e6db74">&#39;a&#39;</span>)
insertLeft(tree,<span style="color:#e6db74">&#39;b&#39;</span>)
insertRight(tree,<span style="color:#e6db74">&#39;c&#39;</span>)
insertRight((getLeftChild(tree)),<span style="color:#e6db74">&#39;d&#39;</span>)
insertLeft((getRightChild(tree)),<span style="color:#e6db74">&#39;e&#39;</span>)
insertRight((getRightChild(tree)),<span style="color:#e6db74">&#39;f&#39;</span>)
</code></pre></div><p><strong>1.2 二叉树的类实现</strong></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">BinaryTree</span>(object):
    <span style="color:#66d9ef">def</span> __init__(self,item):
        self<span style="color:#f92672">.</span>key<span style="color:#f92672">=</span>item
        self<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">=</span>None
        self<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">=</span>None
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insertLeft</span>(self,item):
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">==</span>None:
            self<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">=</span>BinaryTree(item)
        <span style="color:#66d9ef">else</span>:
            t<span style="color:#f92672">=</span>BinaryTree(item)
            t<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>leftChild
            self<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">=</span>t
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insertRight</span>(self,item):
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">==</span>None:
            self<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">=</span>BinaryTree(item)
        <span style="color:#66d9ef">else</span>:
            t<span style="color:#f92672">=</span>BinaryTree(item)
            t<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>rightChild
            self<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">=</span>t
</code></pre></div><h3 id="2-表达式树">2. 表达式树</h3>
<p>表达式树(expression tree)的树叶是操作数，其他节点为操作符。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cbaiodatree.png" alt="img"></p>
<p>图  ((7+3)*(5-2))的表达式树表示</p>
<p><strong>2.1 根据中缀表达式构造表达式树：</strong></p>
<p>遍历表达式：</p>
<p>1.建立一个空树</p>
<p>2.遇到&rsquo;('，为当前的Node添加一个left child，并将left child当做当前Node。</p>
<p>3.遇到数字，赋值给当前的Node，并返回parent作为当前Node。</p>
<p>4.遇到(&lsquo;+-*/')，赋值给当前Node，并添加一个Node作为right child，将right child当做当前的Node。</p>
<p>5.遇到&rsquo;)',返回当前Node的parent。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">buildexpressionTree</span>(exp):
    tree<span style="color:#f92672">=</span>BinaryTree(<span style="color:#e6db74">&#39;&#39;</span>)
    stack<span style="color:#f92672">=</span>[]
    stack<span style="color:#f92672">.</span>append(tree)
    currentTree<span style="color:#f92672">=</span>tree
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> exp:
        <span style="color:#66d9ef">if</span> i<span style="color:#f92672">==</span><span style="color:#e6db74">&#39;(&#39;</span>:
            currentTree<span style="color:#f92672">.</span>insertLeft(<span style="color:#e6db74">&#39;&#39;</span>)
            stack<span style="color:#f92672">.</span>append(currentTree)
            currentTree<span style="color:#f92672">=</span>currentTree<span style="color:#f92672">.</span>leftChild
        <span style="color:#66d9ef">elif</span> i <span style="color:#f92672">not</span> <span style="color:#f92672">in</span> <span style="color:#e6db74">&#39;+-*/()&#39;</span>:
            currentTree<span style="color:#f92672">.</span>key<span style="color:#f92672">=</span>int(i)
            parent<span style="color:#f92672">=</span>stack<span style="color:#f92672">.</span>pop()
            currentTree<span style="color:#f92672">=</span>parent
        <span style="color:#66d9ef">elif</span> i <span style="color:#f92672">in</span> <span style="color:#e6db74">&#39;+-*/&#39;</span>:
            currentTree<span style="color:#f92672">.</span>key<span style="color:#f92672">=</span>i
            currentTree<span style="color:#f92672">.</span>insertRight(<span style="color:#e6db74">&#39;&#39;</span>)
            stack<span style="color:#f92672">.</span>append(currentTree)
            currentTree<span style="color:#f92672">=</span>currentTree<span style="color:#f92672">.</span>rightChild
        <span style="color:#66d9ef">elif</span> i<span style="color:#f92672">==</span><span style="color:#e6db74">&#39;)&#39;</span>:
            currentTree<span style="color:#f92672">=</span>stack<span style="color:#f92672">.</span>pop()
        <span style="color:#66d9ef">else</span>:
            <span style="color:#66d9ef">raise</span> <span style="color:#a6e22e">ValueError</span>
    <span style="color:#66d9ef">return</span> tree
</code></pre></div><p>上述算法对中缀表达式的写法要求比较繁琐，小括号应用太多，例如要写成(a+(b*c))的形式。</p>
<p>用后缀表达式构建表达式树会方便一点:如果符号是操作数，建立一个单节点并将一个指向它的指针推入栈中。如果符号是一个操作符，从栈中弹出指向两棵树T1和T2的指针并形成一棵新的树，树的根为此操作符，左右儿子分别指向T2和T1.</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">build_tree_with_post</span>(exp):
    stack<span style="color:#f92672">=</span>[]
    oper<span style="color:#f92672">=</span><span style="color:#e6db74">&#39;+-*/&#39;</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> exp:
        <span style="color:#66d9ef">if</span> i <span style="color:#f92672">not</span> <span style="color:#f92672">in</span> oper:
            tree<span style="color:#f92672">=</span>BinaryTree(int(i))
            stack<span style="color:#f92672">.</span>append(tree)
        <span style="color:#66d9ef">else</span>:
            righttree<span style="color:#f92672">=</span>stack<span style="color:#f92672">.</span>pop()
            lefttree<span style="color:#f92672">=</span>stack<span style="color:#f92672">.</span>pop()
            tree<span style="color:#f92672">=</span>BinaryTree(i)
            tree<span style="color:#f92672">.</span>leftChild<span style="color:#f92672">=</span>lefttree
            tree<span style="color:#f92672">.</span>rightChild<span style="color:#f92672">=</span>righttree
            stack<span style="color:#f92672">.</span>append(tree)
    <span style="color:#66d9ef">return</span> stack<span style="color:#f92672">.</span>pop()
</code></pre></div><h3 id="3树的遍历">3.树的遍历</h3>
<p><strong>3.1 先序遍历(preorder travelsal)</strong></p>
<p>先打印出根，然后递归的打印出左子树、右子树，对应先缀表达式</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">preorder</span>(tree,nodelist<span style="color:#f92672">=</span>None):
    <span style="color:#66d9ef">if</span> nodelist <span style="color:#f92672">is</span> None:
        nodelist<span style="color:#f92672">=</span>[]
    <span style="color:#66d9ef">if</span> tree:
        nodelist<span style="color:#f92672">.</span>append(tree<span style="color:#f92672">.</span>key)
        preorder(tree<span style="color:#f92672">.</span>leftChild,nodelist)
        preorder(tree<span style="color:#f92672">.</span>rightChild,nodelist)
    <span style="color:#66d9ef">return</span> nodelist
</code></pre></div><p>　　</p>
<p><strong>3.2 中序遍历(inorder travelsal)</strong></p>
<p>先递归的打印左子树，然后打印根，最后递归的打印右子树，对应中缀表达式</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">inorder</span>(tree):
    <span style="color:#66d9ef">if</span> tree:
        inorder(tree<span style="color:#f92672">.</span>leftChild)
        <span style="color:#66d9ef">print</span> tree<span style="color:#f92672">.</span>key
        inorder(tree<span style="color:#f92672">.</span>rightChild)
</code></pre></div><p><strong>3.3 后序遍历(postorder travelsal)</strong></p>
<p>递归的打印出左子树、右子树，然后打印根，对应后缀表达式</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">postorder</span>(tree):
    <span style="color:#66d9ef">if</span> tree:
        <span style="color:#66d9ef">for</span> key <span style="color:#f92672">in</span> postorder(tree<span style="color:#f92672">.</span>leftChild):
            <span style="color:#66d9ef">yield</span> key
        <span style="color:#66d9ef">for</span> key <span style="color:#f92672">in</span> postorder(tree<span style="color:#f92672">.</span>rightChild):
            <span style="color:#66d9ef">yield</span> key
        <span style="color:#66d9ef">yield</span> tree<span style="color:#f92672">.</span>key
</code></pre></div><p><strong>3.4 表达式树的求值</strong></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">postordereval</span>(tree):
    operators<span style="color:#f92672">=</span>{<span style="color:#e6db74">&#39;+&#39;</span>:operator<span style="color:#f92672">.</span>add,<span style="color:#e6db74">&#39;-&#39;</span>:operator<span style="color:#f92672">.</span>sub,<span style="color:#e6db74">&#39;*&#39;</span>:operator<span style="color:#f92672">.</span>mul,<span style="color:#e6db74">&#39;/&#39;</span>:operator<span style="color:#f92672">.</span>truediv}
    leftvalue<span style="color:#f92672">=</span>None
    rightvalue<span style="color:#f92672">=</span>None
    <span style="color:#66d9ef">if</span> tree:
        leftvalue<span style="color:#f92672">=</span>postordereval(tree<span style="color:#f92672">.</span>leftChild)
        rightvalue<span style="color:#f92672">=</span>postordereval(tree<span style="color:#f92672">.</span>rightChild)
        <span style="color:#66d9ef">if</span> leftvalue <span style="color:#f92672">and</span> rightvalue:
            <span style="color:#66d9ef">return</span> operators[tree<span style="color:#f92672">.</span>key](leftvalue,rightvalue)
        <span style="color:#66d9ef">else</span>:
            <span style="color:#66d9ef">return</span> tree<span style="color:#f92672">.</span>key
</code></pre></div>
</div>


    </main>

    
  </body>
</html>
